import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:给定一个包含 n 个整数的数组 nums，
 * 判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
 * User: wangxin
 * Date: 2025-03-14
 * Time: 22:10
 */
public class Test2 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int n = nums.length;
        Arrays.sort(nums);
        for(int first = 0;first < n;++first){
            if(first>0&& nums[first] == nums[first-1]){
                continue;
            }
            int third = n-1;
            int target = -nums[first];
            for(int second = first+1;second < n;++second){
                if(second>first+1&& nums[second] == nums[second-1]){
                    continue;
                }
                while(second < third&&nums[second]+nums[third]>target){
                    --third;
                }
                if(second == third){
                    break;
                }
                if(nums[second]+nums[third] == target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    res.add(list);
                }
            }
        }

        return res;
    }
}
